class Solution
{
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>> &edges)
    {
        int n = edges.size();
        vector<int> inDegree(n + 1, 0);
        vector<int> outDegree(n + 1, 0);
        int target = -1;
        int root = -1;
        for (auto &edge : edges)
        {
            ++inDegree[edge[1]];
            if (inDegree[edge[1]] == 2)
            {
                target = edge[1];
            }
            ++outDegree[edge[0]];
        }
        for (int i = 0; i <= n; ++i)
        {
            if (inDegree[i] == 0)
            {
                root = i;
            }
        }

        auto check = [&](int ignore) -> bool
        {
            vector<vector<int>> children(n + 1);
            for (int i = 0; i < n; ++i)
            {
                if (i == ignore)
                {
                    continue;
                }
                children[edges[i][0]].push_back(edges[i][1]);
            }

            int visited = 0;
            queue<int> q;
            q.push(root);
            while (!q.empty())
            {
                int node = q.front();
                q.pop();
                ++visited;
                for (auto child : children[node])
                {
                    q.push(child);
                }
            }
            return visited == n;
        };

        for (int i = n - 1; i >= 0; --i)
        {
            auto &edge = edges[i];
            int s = edge[0];
            int t = edge[1];

            if (target == -1)
            {
                root = t;
                if (check(i))
                {
                    return edge;
                }
            }
            else if (t == target)
            {
                if (check(i))
                {
                    return edge;
                }
            }
        }
        return {};
    }
};